/**
 * 背包问题(动态规划算法)
 *
 * @Author: wanqian
 * @Date: 2021/2/26 13:29
 */
public class KnapsackProblemDemo {

    public static void main(String[] args) {
        //物品重量
        int[] weight = {1, 4, 3};
        //物品价值
        int[] val = {1500, 3000, 2000};
        //背包容量
        int m = 4;
        //物品数量
        int n = val.length;
        //记录物品放入
        int[][] path = new int[n + 1][m + 1];
        //创建表格
        int[][] v = new int[n + 1][m + 1];
        //i表示第几个物品，j表示背包容量
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                // 如果物品重量大于背包容量，则不装入背包
                // 最大价值为上一个物品的最大价值
                if (weight[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - weight[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - weight[i - 1]];
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }

        // path记录的是最优解是否放入当前商品
        // 1. 从后往前，先判断当前背包容量下是否放入最后一个商品
        // 2. 若放入，则将i--（考虑上一个物品）, j=j-weight[i-1](剩余背包容量)
        // 3. 即剩余背包容量下，是否放入上一个商品。若最优解是放入，则继续第2步。
        // 4. 若不放入，则i--, 即不考虑当前物品。
        int i = path.length - 1; // 行的最大下标
        int j = path[0].length - 1; // 列的最大下标
        while (i > 0 && j > 0) { // 从path的最后开始找
            if (path[i][j] == 1) {
                System.out.printf("第%d个商品放入到背包\n", i);
                j -= weight[i - 1]; // w[i-1]
            }
            i--;
        }
    }

}
